Error diffusion is the most commonly used FM screening method. According to this method, when the gray levels of each pixel point of a source image are compared with a threshold to generate screen dots, the errors between the gray levels of the pixel points and the threshold are diffused to pixel points around the pixel point. For example, for a image with 256 gray level, the threshold is 127, the gray level of a certain pixel point is 150, and upon comparison, the pixel point should be recorded as a white screen dot (the gray level of a white screen dot is 255), while actually this pixel point is not really white and has an error value of 105 with the real white color, and then the error of 105 is diffused to the pixel points around this pixel point in a certain method. Common error diffusing methods are Floyd-Steinberg algorithm, and Jarvis algorithm.
Floyd-Steinberg algorithm refers to allocating the error of one pixel to four pixel points surrounding it. That is, 7/16 of the error is added to the first pixel point in the right of the current pixel point, 5/16 of the error is added to the pixel point in the next row over against the current pixel point, 3/16 of the error is added to the neighboring pixel point in the left of the pixel point in the next row over against the current pixel point, and 1/16 of the error is added to the neighboring pixel point in the right of the pixel point in the next row over against the current pixel point. This process is performed repeatedly, and the same correction of the gray levels and the half toning are performed to each pixel point in the image.
Jarvis algorithm is to allocate the error of a current pixel X to 12 neighboring pixels, as shown in FIG. 1A. The error allocation ratios of some locations among the 12 locations are the same, so only 4 different error allocation ratios are needed, wherein the error of the current pixel X can be allocated in the ratios of D1=1/48, D2=3/48, D3=5/48, and D4=7/48. Although the image half toning processing based on Jarvis error diffusing method can achieve better effect by expanding the scope of error diffusion, the error diffusion according to this method relates to more row and more pixel points, which leads to increasing the storage capacity and slowing the speed, therefore it cannot meet real-time demands and then the application field is limited.
In addition, during error diffusion using the above-mentioned algorithm, if the source image is always only processed via single-direction scanning, the error of each scanned row would be simply added to the next row, which leads to error accumulation that is represented by a driving tendency of the image in the output pattern. Hence, during scanning, a ‘S’ shaped scanning is usually adopted, i.e. scanning from let to right for odd number rows, as shown in FIG. 1A; and scanning from right to left for even number rows, as shown in FIG. 1B (or on the contrary). Scanning is repeated in this manner till the last row.
China patent application No. CN 200510063255.3 discloses a method for generating FM screen dots at high speed (published on Sep. 14, 2005), and this method lowers the operation times of memory while can only process image pixel by pixel, and also, this method cannot process multiple pixels and generate multiple screen dots simultaneously.
US patent application entitled “Multi-dimensional error diffusion technique” (U.S. Pat. No. 5,271,070) discloses a parallel processing method for error diffusion. Although this method can process a plurality of pixel points, it needs to perform multiple read/write operations on the memory, and the ‘S’ shaped image scanning cannot be performed on the source image, which affects the generating speed of the screen dots, which is unhelpful to eliminate the driving effect resulting from the error accumulation.